package tree

// https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvix0d/
// 从前序遍历和中序遍历中构造树
// 算法: 递归
// 前提：树中没有重复的元素
// 当前: WA
// 前序: [3,9,20,15,7]
// 中序: [9,3,15,20,7]
func BuildTree(preorder []int, inorder []int) *TreeNode {
	// 递归构造树
	return recurBuildTree(preorder, inorder, 0, 0, len(preorder))
}

func recurBuildTree(preorder []int, inorder []int, preStart, inStart, treeLen int) *TreeNode {
	if len(preorder) == 0 || preStart >= len(preorder) || inStart >= len(inorder) || treeLen <= 0 {
		return nil
	}

	toFindInOrderNum := preorder[preStart]
	var inPos = 0
	for index := inStart; index < len(inorder); index++ {
		if inorder[index] == toFindInOrderNum {
			inPos = index
			break
		}
	}

	var leftLen = inPos - inStart

	head := new(TreeNode)
	head.Val = toFindInOrderNum
	head.Left = recurBuildTree(preorder, inorder, preStart+1, inStart, leftLen)
	head.Right = recurBuildTree(preorder, inorder, preStart+leftLen+1, inPos+1, treeLen-leftLen-1)
	return head
}
